package Test;
import java.util.*;
public class Test08 {
    //摆动序列贪心算法
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if(n < 2) return 1;
        int ret = 0;
        int left = 0;

        for(int i = 0;i< n-1;i++){
            int right = nums[i+1]-nums[i];
            if(right == 0) continue; // 如果⽔平，直接跳过
            if(left * right <= 0) ret++; // 累加波峰或者波⾕
            left = right;
        }
        return ret+1;
    }
    //贪心算法的最大数问题
    public String largestNumber(int[] nums) {
        //将数字转换为字符串
        int n = nums.length;
        String[] str = new String[n];
        for(int i = 0;i<n;i++) str[i] = ""+nums[i];
        Arrays.sort(str,(a,b)->{
            return (b+a).compareTo(a+b);
        });
        StringBuffer ss = new StringBuffer();
        for(String s : str) ss.append(s);
        String ret = ss.toString();
        if(ret.charAt(0) == '0') return "0";
        return ret;
    }
    //粉刷房子
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n+1][3];
        for(int i = 1;i<=n;i++){
            //有许多相似的代码我们需要复制节省时间
            //但是细节需要看清 ,
            //比如这道题,各种位置的不同颜色的粉刷价格不同
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + costs[i-1][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + costs[i-1][1];
            dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0]) + costs[i-1][2];
        }
        int ret = Math.min(dp[n][0],Math.min(dp[n][1],dp[n][2]));
        return ret;
    }
    //地下城dp问题
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 0;i<=m;i++) dp[i][n] = Integer.MAX_VALUE;
        for(int j = 0;j<=n;j++) dp[m][j] = Integer.MAX_VALUE;
        //初识值要正确
        //因为健康点数最小为1
        dp[m][n-1] = dp[m-1][n] = 1;
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                //为什么要与1做比较呢?
                //因为可能为负数 , 健康点数不能为负数
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
    //贪心算法 , 买股票最佳时机II
    public int maxProfit(int[] prices) {
        int ret = 0;
        int n = prices.length;
        for(int i = 0;i<n-1;i++){
            if(prices[i] < prices[i+1]) ret += (prices[i+1]-prices[i]);

        }
        return ret;
    }
    //柠檬水找零
        public boolean lemonadeChange(int[] bills) {
            // HashMap<Integer,Integer> map = new HashMap<>();
            int[] map = new int[21];
            int n = bills.length;
            for(int i = 0;i<n;i++){
                if(bills[i] == 5) map[5]++;
                else if(bills[i] == 10) {
                    map[10]++;
                    if(map[5] == 0) return false;
                    else map[5]--;
                } else {
                    int temp = 15;
                    if(map[10] != 0) {
                        temp-=10;
                        map[10]--;
                    }
                    while(temp != 0){
                        if(map[5] != 0){
                            map[5]--;
                            temp-=5;
                        }else{
                            return false;
                        }
                    }
                }
            }
            return true;
        }

    //串联最小的子串
        public List<Integer> findSubstring(String s, String[] words) {
            //定义返回值
            List<Integer> ret = new ArrayList<>();
            //哈希表统计字符串
            HashMap<String,Integer> map1 = new HashMap<>();
            for(String str : words) map1.put(str,map1.getOrDefault(str,0)+1);
            //在words中每个单词的字母长度一样
            //从例子中得出来的
            int len = words[0].length();
            int words_len = words.length;
            for(int i = 0;i < len;i++){
                //下面要写到循环中,因为一个s中可能出现多个words的组合
                //局部变量自己进行初始化操作
                HashMap<String,Integer> map2 = new HashMap<>();
                for(int l = i,r = i,count = 0;r + len <= s.length();r+=len){
                    //进窗口
                    String in = s.substring(r,r+len);
                    map2.put(in,map2.getOrDefault(in,0)+1);
                    if(map2.get(in) <= map1.getOrDefault(in,0)) count++;
                    //判断条件出窗口
                    if(r - l + 1 > len * words_len){
                        String out = s.substring(l,l+len);

                        // map2.put(out,map2.get(out)-1);
                        if(map2.get(out) <= map1.getOrDefault(out, 0))
                            count--;
                        //下面不用使用getOrDefault,因为不可能出现0的情况
                        map2.put(out, map2.get(out) - 1);
                        l += len;
                    }
                    //进行更新结果
                    if(count == words_len) ret.add(l);
                }
            }
            return ret;
        }

    public int change(int amount, int[] coins)
    {
        // 空间优化
        int[] dp = new int[amount + 1]; // 建表
        dp[0] = 1; // 初始化
        for(int x : coins) // 拿出物品
            for(int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置
                dp[j] += dp[j - x];
        return dp[amount];
    }
}
